package _interview75;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 2542. 最大子序列的分数
 */
public class No2542 {
    /*
      要用long,否则溢出提交报错
      本解法其实也是暴力算法,遍历所有情况,只不过是采用了排序和最小堆的方式确立一个遍历的方式
      从审题我们知道这都是正整数,如果不是的话,排序毫无意义了,因为负负得正,有可能更高,
      既然都是正整数,那么乘法的权重肯定是要比加法的权重要高得多的,所以我们先给nums2来降序, 降序之后,
      此时,k就能翻译成nums2的前k个
     */
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;

        int[][] numsArr = new int[n][2];
        for (int i = 0; i < n; i++) {
            numsArr[i][0] = nums1[i];
            numsArr[i][1] = nums2[i];
        }
        Arrays.sort(numsArr, (o1, o2) -> o2[1] - o1[1]);

        long res = 0L;
        // 最小堆
        Queue<Integer> num1Heap = new PriorityQueue<>();
        long num1Sum = 0;
        for (int[] nums : numsArr) {
            // nums1是被动的跟随nums2取值的
            int num1 = nums[0], num2 = nums[1];

            // 这个是k个元素都够了以后,还要继续遍历的时候才会进入,比如前k是4 3 2的时候,最小的是2,那么向下移动一个位置,变成3 2 1的时候,该把nums1里的谁踢掉呢,
            // 此时,因为nums2有了1的加入,1是最小的了,在k里的num2的其他元素在min()函数里没有意义了,此时看公式的另一项了,num1还是有作用的,因此去掉num1构件的最小堆里最小的值,也就是1
            // nums2  nums1          nums2   nums1
            // * * *                 * * *
            // * 4 *     2           * 4 *      2
            // * 3 *     3           * 3 *      3
            // * 2 *     1   >>>     * * *
            // * * *                   2        1 //这个从最小堆中踢掉
            //   1       3           * * *
            //                       * 1 *      3
            //                       * * *
            if (num1Heap.size() == k) num1Sum -= num1Heap.poll();

            num1Heap.offer(num1);
            num1Sum += num1;
            // 当符合这个条件时,y刚好就是前k个元素里最小的
            if (num1Heap.size() == k) res = Math.max(res, num1Sum * num2);
        }

        return res;
    }
}